Release 63.0 of the national nucleic acid data base, Genbank, contains over forty million nucleotides representing about thirty-three thousand separate entries. Similarly, the current protein information resource (PIR) has close to six thousand entries with over one and one-half million amino acids. These data reflect primarily the efforts of the molecular biology community over the last decade. The rate at which new data are being added to this total demonstrates that the available computing resources are already inadequate for thorough and timely analysis of the data. Recently, an international commitment has been made to map and sequence the entire human genome in the next 10 to 20 years. Such a program will generate at least 3.4 billion nucleotides of final data and maybe ten times that amount of raw sequencing data. This constitutes about three orders of magnitude more data than has been collected to date. In addition, the sequences from other animal and plant genomes will also accumulate. In the near term, the 40 million nucleotides currently available and already proving burdensome, will become trivial by comparison to the total. Novel computer resources must be developed if these data are to be adequately understood and their unique potential for enhancing our understanding of human genetics and diseases are to be realized.
A required adjunct to any program designed to characterize the human genome is the development of computer hardware and software systems capable of maintaining and analyzing the vast amounts of information that will be generated. This information will consist of both nucleotide and amino acid sequence data as well as extensive annotation necessary to provide a biological context for these data. It is critical for the complete and timely analysis of new sequence data, that they be thoroughly compared to the published data contained in the national data libraries. This analysis is important for determining and defining the functional and evolutionary relationships between sequences. Significantly, such sequence comparison is also critical to the task of constructing the complete genome sequence from millions of partially overlapping fragments, the so-called melding process. The computational load of this melding process will grow not only at the national level of coordinating the efforts of many researchers, but also at the level of individual laboratories that must deal with the increasing load of raw data generated by the development of automated sequencing technologies.
The ability of individual investigators to analyze their own data is limited by the power of the computers they have available, as well as the limited software tools capable of dealing with the entire sequence library. The amount of total sequence data generated to date is still less than 50 million character equivalents. However, this amount of data already taxes the ability of currently available algorithms and general use computers to conduct the needed comparative analysis of new data to the collected total. The data libraries have been doubling in size every year. The program that is envisioned to characterize complete genomes, will soon cause the data libraries to increase exponentially. Such programs will also change the basic nature of the collected data and consequently the requirements for effective tools for its analysis.
In the latest Genbank release, the average length of an individual entry can span over one million bases. Many of the current methods of analyzing this data are based on the notion that each entry represents a discrete genetic element. However, this scenario does not adequately represent the more diffuse and complex organization of a eukaryotic genome, where the coding and regulatory elements of a simple gene can span more than one million bases. More complex loci, such as those coding for the rearranging receptors of the immune system, can span over one million bases and include hundreds or thousands of identifiably related elements. As more and larger sequencing efforts are undertaken, the complexity of information contained in single entries will require a novel set of maintenance and analytical tools.
The human beta globin locus is a good example. Its entry in Genbank is over 73 thousand bases long and has been constructed from over 70 overlapping contributions. This single entry contains the coding and regulatory information for at least 4 genes and 1 pseudogene. The repetitive nature of much of the genome will also severely complicate the alignment and melding problems. With megabase sequencing projects, the current concept of data entry will become obsolete. Not only will faster algorithms to compare sequences be needed as the amount of data increases, but these new tools will also have to be designed to better deal with longer strings of data that more directly reflect true genomic organization. Accordingly, novel schemes to handle and define these data and the biological information associated with them must be developed if this resource is to be useful to the scientific community.
Of the many pressing and analytical needs concerning the current sequence data libraries, as well as the genome project, initially the most significant is the ability to survey the existing collection of data for sequences related to the new data. In its simplest form, this need is illustrated by searching the collection of gene or protein sequences for any that are "similar" to a discrete piece of new data. The comparative analyses possible between related sequences are critical for completely understanding the structural, functional and evolutionary characteristics of any sequence. Furthermore, in the case where large portions of the human genome are known, it will also be necessary to have the ability to find the precise genetic location of physiological markers in those cases where there may be only limited CDNA or protein sequence data available.
Such searches are complicated by the fact that related sequences may be quite divergent. This means that it is essential to define some measure of similarity between pairs of sequences that can then be tested statistically. The explicit series of minimal evolutionary events (substitutions, deletions, insertions) between two sequences must be determined; i.e., the sequences must be aligned. Traditionally, the most common method of alignment has been by eye, relying on the researcher's ability to recognize conserved patterns. This method can be rapid and effective when the sequence distance is relatively small and/or the researcher has a priori information about the probable nature of the alignment. For example, many new members of the immunoglobulin gene superfamily have been identified and aligned to other members on the basis of a very limited, but well-defined set of conserved features. However, it is certainly no longer possible for any investigator to reliably compare a novel sequence against a significant portion of the existent data base.
It is possible in theory to generate every possible combination of genetic events between two sequences, score each one and discover the most similar. This is in practice, impossible for all but the shortest sequences however, as the combinations increase exponentially with the length of the sequences. Some investigators have implemented rule-based methods by which, given a reasonable starting alignment point, gaps and insertions are included according to a very restricted set of possibilities. These methods can be relatively rapid, but, like manual alignment, are non-rigorous methods as they cannot predictably guarantee that the results represent the optimal minimum distance, that is, the minimum evolutionary distance between two sequences or the series of events that provides the smallest weighted sum required to transform one sequence into the other.
When the assumption is that two sequences are generally similar along their entire length, the alignment process is considered to be global in nature. However, an alignment proceeding from this premise can fail to recognize more limited regions of similarity between two otherwise unrelated sequences. What is required then is the ability to find all regions of local alignment. For example, if an investigator has a new sequence related to a human beta globin gene, such as one from another species, the need is to be able to find the local alignment of that more limited sequence to some particular portion of the 73 thousand base of the known beta globin locus. The same concerns are manifest in the melding problem. By definition, most overlapping sequences will only share a limited region of identity, illustrating a local alignment problem.
In 1970, S. B. Needleman and C. D. Wunsch authored a paper entitled "A General Method Applicable To The Search For Similarities In The Amino Acid Sequence Of Two Proteins", which was published in the Journal of Molecular Biology, Volume 48, Page 444. Their paper has had a great deal of influence in biological sequence alignment. Its particular advantage is that an explicit criterion for optimality of alignment is stated and an efficient method of solution is given. Insertions, deletions and mismatches were allowed in the alignments. The method of Needleman and Wunsch fit into a broad class of algorithms, commonly referred to as dynamic programming. The general category of dynamic programming alignment of two sequences is discussed at length in a text entitled "Mathematical Methods for DNA Sequences" and particularly Chapter 3 thereof, entitled "Sequence Alignments" written by Michael S. Waterman, of the University of Southern California.
In 1980, Dr. Waterman, then with the Los Alamos Scientific Laboratory, collaborated with T. F. Smith, then a Professor at Northern Michigan University, in publishing a letter entitled "Identification of Common Molecular Subsequences" which appeared in the Journal of Molecular Biology, Volume 147, pages 195-197, 1981. In this letter, Waterman and Smith defined a new algorithm, the intention of which was to find a pair of segments, one from each of two long sequences, such that there was no other pair of segments with greater similarity (or "homology"). The algorithm produced a similarity measure which allowed for arbitrary length, deletions and insertions.
In a more recent publication, entitled "A New Algorithm for Best Subsequence Alignments With Application to tRNA-rRNA Comparisons", Waterman and Mark Eggert, in the Journal of Molecular Biology, Volume 197, pages 723-728, (1987), describe the efficiency of the algorithm of Smith and Waterman for identification of maximally similar subsequences. The article describes the use of the algorithm in which alignments of interest are produced first for the best alignment and then making small modifications to the matrix for producing non-intersecting subsequent alignments. The algorithm is applied to comparisons of tRNA-rRNA sequences from escherichia coli. A statistical analysis therein shows results which differ substantially from the results of an earlier analysis by others and furthermore, that the algorithm is much simpler and more efficient than those previously in use.
The need for low cost, high speed data sequence comparisons cannot be met even with current supercomputers because of existing data base size. There is therefore an existing need to provide an electronic circuit device for carrying out subsequence alignments of molecular sequences or global alignment thereof and more specifically for a sequence information signal processor designed to carry out a dynamic programming algorithm which is both effective and efficient in identifying subsequence or global alignments of molecular information. Such an electronic circuit device, to be reliable, should have the capability to quickly and efficiently detect hardware faults and thereafter automatically bypass such faults so that the aforementioned alignments can continue in an accurate and reliable manner despite such faults.
The following U.S. Pat. Nos. are relevant to fault detection and bypass.
U.S. Pat. No. 3,649,963 Holm et al PA1 U.S. Pat. No. 3,898,621 Zelinski et al PA1 U.S. Pat. No. 4,039,813 Kregness PA1 U.S. Pat. No. 4,233,682 Liebergot et al PA1 U.S. Pat. No. 4,242,751 Henckels et al PA1 U.S. Pat. No. 4,347,608 Appiano et al PA1 U.S. Pat. No. 4,358,823 McDonald et al PA1 U.S. Pat. No. 4,675,646 Lauer PA1 U.S. Pat. No. 4,710,932 Hiroshi PA1 U.S. Pat. No. 4,726,024 Guziak et al PA1 U.S. Pat. No. 4,730,319 David et al PA1 U.S. Pat. No. 4,745,542 Baba et al PA1 U.S. Pat. No. 4,757,503 Hayes et al PA1 U.S. Pat. No. 4,768,196 Jou et al PA1 U.S. Pat. No. 4,821,176 Ward et al PA1 U.S. Pat. No. 4,837,765 Suzuki PA1 U.S. Pat. No. 4,839,897 Aoki PA1 U.S. Pat. No. 4,849,979 Maccianti et al PA1 U.S. Pat. No. 4,916,695 Ossfeldt
U.S. Pat. No. 4,849,979 to Maccianti et al is directed to a fault tolerant computer architecture. The multi-processor system is constructed from functional units which are duplicated and where the input and output signals are compared with each other, non-agreement resulting in an error signal.
U.S Pat. No. 4,745,542 to Baba et al is directed to a fail-safe control circuit. The controlled unit is intended to operate only when all control units provide an identical input. The AND gate is coupled to each of the operation control units for comparing the outputs therefrom.
U.S. Pat. No. 4,039,813 to Kregness is directed to a self-test monitor and diagnostic system. The system includes a memory sequentially addressed by a counter for generating stored diagnostic code words.
U.S. Pat. No. 4,710,932 to Hiroshi is directed to a fault detection system. The signal generator provides sequential test signals to both the tested circuit and a delay circuit, as similarly does the signal generator, supplying test signals to the reference circuit and similar delay circuits. The output from each test set-up is compared by the comparator for determining whether the circuit under test provides identical outputs to that of the referenced circuit.
U.S. Pat. No. 4,358,823 to McDonald et al is directed to a double-redundant processor having fault detection Each of the processors includes sub-processors which simultaneously execute the same data, control and address signals, and thus should produce the same output signals. The output from each of the sub-processors are compared by a comparator whose output is utilized to trigger an alarm monitor if agreement is not provided by the outputs of the sub-processors.
U.S. Pat. No. 4,837,765 to Suzuki is directed to a test control circuit for integrated circuits. Referring to the embodiment of FIG. 3, there is shown AND gates provided for comparing test signals provided by the selector circuits.
U.S. Pat. No. 4,726,024 to Guziak et al is directed to a failsafe architecture for a computer system. The system periodically actuates a self-check module for testing the microprocessor.
U.S. Pat. No. 4,233,682 to Liebergot et al is directed to a fault detection and isolation system. A single integrated circuit chip includes duplicate functional logic chains, each receiving input signals in parallel, and whose outputs are compared by a comparator for indicating an error condition in one of the functional circuits.